//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2012 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#include <buola/container/cintrusiverbtree.h>
#include <vector>
#include <set>
#include <boost/intrusive/set.hpp>
#include <boost/interprocess/offset_ptr.hpp>
#include <buola/memory/offset_ptr.h>
#include <buola/io.h>

static const int NUM_RANGE=1000000;
static const int VEC_SIZE=1000000;

namespace bi=boost::intrusive;

struct CBInt : public bi::set_base_hook<bi::link_mode<bi::normal_link>,bi::void_pointer<boost::interprocess::offset_ptr<void> > >
{
    CBInt(int pI,int pIndex)
        :   mI(pI)
        ,   mIndex(pIndex)
    {}
    
    int mI;
    int mIndex;
};

struct CInt;
typedef buola::CIntrusiveRBTree<CInt,true,std::less<CInt>,buola::offset_ptr<CInt> > TBuolaTree;
//typedef buola::CIntrusiveRBTree<CInt,true,std::less<CInt>,CInt*> TBuolaTree;

struct CInt : public TBuolaTree::SHook
{
    CInt(int pI,int pIndex)
        :   mI(pI)
        ,   mIndex(pIndex)
    {}
    
    int mI;
    int mIndex;
};

bool operator<(const CInt &pLH,const CInt &pRH)
{
    return pLH.mI<pRH.mI;
}

bool operator<(const CBInt &pLH,const CBInt &pRH)
{
    return pLH.mI<pRH.mI;
}

bool operator==(const CInt &pLH,const CInt &pRH)
{
    return pLH.mI==pRH.mI;
}

bool operator==(const CBInt &pLH,const CBInt &pRH)
{
    return pLH.mI==pRH.mI;
}

buola::io::CTextWriter &operator<<(buola::io::CTextWriter &pW,const CInt &pInt)
{
    pW << pInt.mI << "(" << pInt.mIndex << ")";
    return pW;
}

int main()
{
    using namespace buola;
    
    msg_info() << sizeof(CInt) << "," << sizeof(CBInt) << "\n";
//    srand(time(NULL));
    
    std::vector<CInt> lVector;
    std::vector<CBInt> lBVector;
    
    buola::start_timer();
    for(int i=0;i<VEC_SIZE;i++)
    {
        int lI=rand()%NUM_RANGE;
        lVector.emplace_back(lI,i);
        lBVector.emplace_back(lI,i);
    }
    
    buola::end_timer();
    
    std::vector<int> lSortedVector;

    buola::start_timer();
    for(auto &i:lVector)
        lSortedVector.push_back(i.mI);
    std::sort(lSortedVector.begin(),lSortedVector.end());
    buola::end_timer();

    msg_info() << lVector.size() << "\n";
    
    int lCount;
    
    msg_info() << "buola\n";
    TBuolaTree lRBTree;
    buola::start_timer();
    for(auto &i:lVector)
        lRBTree.InsertEqual(i);
    buola::end_timer();

    lRBTree.CheckBalance();
    lRBTree.CheckOrder();

    buola::start_timer();
    lCount=0;
    for(auto &i:lVector)
    {
        if(*lRBTree.lower_bound(i)==i)
            lCount++;
    }
    buola::end_timer();
    msg_info() << lCount << "\n";

    buola::start_timer();
    lCount=0;
    for(auto &i:lVector)
    {
        auto j=lRBTree.upper_bound(i);
        if(j!=lRBTree.cend()&&!(*j==i))
            lCount++;
    }
    buola::end_timer();
    msg_info() << lCount << "\n";

    buola::start_timer();
    lCount=0;
    for(int i=0;i<NUM_RANGE;i++)
    {
        CInt lI(i,0);
        if(lRBTree.find(lI)!=lRBTree.cend())
            lCount++;
    }
    buola::end_timer();
    msg_info() << lCount << "\n";
    
    buola::start_timer();
    lCount=0;
    for(int i=0;i<NUM_RANGE;i++)
    {
        CInt lI(i,0);
        lCount+=lRBTree.count(lI);
    }
    buola::end_timer();
    msg_info() << lCount << "\n";
    
    buola::start_timer();
    lCount=0;
    for(int i=0;i<VEC_SIZE/2;i++)
    {
        lCount+=lRBTree.erase(lVector[i]);
    }
    buola::end_timer();
    msg_info() << lCount << "\n";
    
    lRBTree.CheckBalance();
    lRBTree.CheckOrder();

    buola::start_timer();
    lCount=0;
    for(int i=0;i<NUM_RANGE;i++)
    {
        CInt lI(i,0);
        lCount+=lRBTree.count(lI);
    }
    buola::end_timer();
    msg_info() << lCount << "\n";

    msg_info() << "trying iterators now\n";
    lCount=0;
    for(auto i=lRBTree.begin();i!=lRBTree.end();++i)
    {
        ++lCount;
    }
    msg_info() << lCount << "\n";
    lCount=0;
    for(auto i=lRBTree.rbegin();i!=lRBTree.rend();++i)
    {
        ++lCount;
    }
    msg_info() << lCount << "\n";
    lCount=0;
    for(auto i=lRBTree.end();i!=lRBTree.begin();)
    {
        --i;
        ++lCount;
        
    }
    msg_info() << lCount << "\n";

    msg_info() << "boost\n";
    bi::multiset<CBInt> lBMultiset;
    buola::start_timer();
    for(auto &i:lBVector)
        lBMultiset.insert(i);
    buola::end_timer();
    
    buola::start_timer();
    lCount=0;
    for(auto &i:lBVector)
    {
        if(*lBMultiset.lower_bound(i)==i)
            lCount++;
    }
    buola::end_timer();
    msg_info() << lCount << "\n";

    buola::start_timer();
    lCount=0;
    for(auto &i:lBVector)
    {
        auto j=lBMultiset.upper_bound(i);
        if(j!=lBMultiset.cend()&&!(*j==i))
            lCount++;
    }
    buola::end_timer();
    msg_info() << lCount << "\n";

    buola::start_timer();
    lCount=0;
    for(int i=0;i<NUM_RANGE;i++)
    {
        CBInt lI(i,0);
        if(lBMultiset.find(lI)!=lBMultiset.cend())
            lCount++;
    }
    buola::end_timer();
    msg_info() << lCount << "\n";

    buola::start_timer();
    lCount=0;
    for(int i=0;i<NUM_RANGE;i++)
    {
        CBInt lI(i,0);
        lCount+=lBMultiset.count(lI);
    }
    buola::end_timer();
    msg_info() << lCount << "\n";

    buola::start_timer();
    lCount=0;
    for(int i=0;i<VEC_SIZE/2;i++)
    {
        lCount+=lBMultiset.erase(lBVector[i]);
    }
    buola::end_timer();
    msg_info() << lCount << "\n";

    buola::start_timer();
    lCount=0;
    for(int i=0;i<NUM_RANGE;i++)
    {
        CBInt lI(i,0);
        lCount+=lBMultiset.count(lI);
    }
    buola::end_timer();
    msg_info() << lCount << "\n";

    std::multiset<CInt> lMultiSet;
    buola::start_timer();
    for(auto &i:lVector)
        lMultiSet.insert(i);
    buola::end_timer();
}